package basic.courseLearn02.sort;

import basic.courseLearn01.utils.FunctionSort;
import basic.courseLearn01.utils.SortUtils;
import org.junit.Test;

//归并排序
public class MergeSort implements FunctionSort {

    @Override
    public int[] sort(int[] result) {
        return this.mergeSort(result,0,result.length-1);
    }

    @Test
    public void test(){
        SortUtils.executeCheckAlgorithm(1_0000,1000,1000,this);
    }

    public int[] mergeSort(int[] result,int leftIndex,int rightIndex){
        if (leftIndex == rightIndex){   //如果只有一个值，返回该值
            return new int[]{result[leftIndex]};
        }
        int center = leftIndex +((rightIndex-leftIndex)>>1);
        //返回合并的结果
        return merge(mergeSort(result,leftIndex,center),
                mergeSort(result,center+1,rightIndex));
    }


    //合并操作
    public int[] merge(int[] arr1,int[] arr2){
        int[] result=new int[arr1.length+arr2.length];
        int i=0,j=0,k=0;    //i指向arr1，j指向arr2,k指向result
        while(i<arr1.length && j<arr2.length){
            result[k++]=(arr1[i]<arr2[j])?arr1[i++]:arr2[j++];
        }
        while(i<arr1.length){
            result[k++]=arr1[i++];
        }
        while(j<arr2.length){
            result[k++]=arr2[j++];
        }
        return result;
    }

}
